package Solutions;
import java.util.*;

/**
 * @Classname PreorderTree
 * @Description TODO
 * @Date 2021/6/18 16:14
 * @Created by ASUS
 */
public class  PreorderTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> _preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) stack.push(cur.left);
            if (cur.left != null) stack.push(cur.left);
        }
        return res;
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(root, list);
        return list;
    }

    private void preorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.addFirst(cur.val);
            if (cur.left != null) stack.push(cur.left);
            if (cur.right != null) stack.push(cur.right);
        }
        return res;
    }

    public List<Integer> _inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    public boolean _isSymmetric(TreeNode root) {
        StringBuilder sb  = new StringBuilder();
        inpreorder(root, sb);
        String tmp = sb.toString();
        System.out.println(tmp);
        int start = 0, end = tmp.length() - 1;
        while (start < end) {
            if (tmp.charAt(start) != tmp.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

    private void inpreorder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#");
            return;
        }
        if (root.left == null && root.right == null) {
            sb.append(root.val);
            return;
        }
        inpreorder(root.left, sb);
        sb.append(String.valueOf(root.val));
        inpreorder(root.right, sb);
    }

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        return false;
    }

    private void cengci(TreeNode root, Queue<TreeNode> queue) {
        if (root == null) return;
        int current;//当前层 还未打印的结点个数
        int next;//下一层结点个数
        queue.offer(root);
        current = 1;
        next = 0;
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            sb.append(cur.val);
            current--;
            if (cur.left != null) {
                queue.offer(cur.left);
                next++;
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                next++;
            }
            if (current == 0) {
                sb.append("\n");
                current = next;
            }
        }
        if (root.left != null) queue.offer(root.left);
        if (root.right != null) queue.offer(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2,new TreeNode(2), null), new TreeNode(2,new TreeNode(2), null));
        System.out.println(new PreorderTree().isSymmetric(root));
    }

    public void printTree(TreeNode root){
        if(root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();

        int current;//当前层 还未打印的结点个数
        int next;//下一层结点个数

        queue.offer(root);
        current = 1;
        next = 0;
        while(!queue.isEmpty()){
            TreeNode currentNode = queue.poll();
            System.out.printf("%-4d", currentNode.val);
            current--;

            if(currentNode.left != null){
                queue.offer(currentNode.left);
                next++;
            }
            if(currentNode.right != null){
                queue.offer(currentNode.right);
                next++;
            }
            if(current ==0){
                System.out.println();
                current = next;
                next = 0;
            }
        }
    }
}
